package com.leetcode.根据数据结构分类.并查集;


import java.util.HashSet;

/**
 * @author: ZhouBert
 * @date: 2021/1/7
 * @description: 547. 省份数量
 * https://leetcode-cn.com/problems/number-of-provinces/
 */
public class B_547_省份数量 {

	/**
	 * 这是一个典型的 adjacency matrix 邻接数组
	 * 在没有好好学习图的知识之前，先用 union find 的知识点实现一遍。
	 * 1.构建 union find 对 adjacency matrix 进行遍历中 union;(不用 rank 而是用路径压缩)
	 * 2.遍历 union find 中有多少根节点。
	 * --
	 * 好的，一遍过，看来还是昨天 B_399_除法求值 比较厉害！
	 * @param isConnected
	 * @return
	 */
	public int findCircleNum(int[][] isConnected) {
		InnerUnionFind unionFind = new InnerUnionFind(isConnected.length);
		for (int i = 0; i < isConnected.length; i++) {
			for (int j = i + 1; j < isConnected[i].length; j++) {
				//相连
				if (isConnected[i][j] == 1) {
					unionFind.union(i, j);
				}
			}
		}
		//1.让每个节点进行一次 find
		for (int i = 0; i < isConnected.length; i++) {
			unionFind.find(i);
		}
		//遍历 parents 找到不同的节点
		HashSet<Integer> count=  new HashSet<>();
		for (int i = 0; i < unionFind.parents.length; i++) {
			count.add(unionFind.parents[i]);
		}
		return count.size();
	}

	class InnerUnionFind {
		public int[] parents = null;

		public InnerUnionFind(int capacity) {
			this.parents = new int[capacity];
			//初始化每一个点为孤立
			for (int i = 0; i < capacity; i++) {
				parents[i] = i;
			}
		}


		public void union(int i, int j) {
			int pi = find(i);
			int pj = find(j);
			if (pi == pj) {
				return;
			}
			//让 pi 指向 pj(pj 作为 pi 的根节点)
			parents[pi] = parents[pj];
		}

		/**
		 * 找到 i 索引下 元素的根节点
		 *
		 * @param i
		 * @return
		 */
		public int find(int i) {
			int root = i;
			//找到 root
			while (root != parents[root]) {
				root = parents[root];
			}

			//进行路径压缩
			int res = i;
			int prev = i;
			while (res != parents[res]) {
				prev = res;
				res = parents[res];
				parents[prev] = root;
			}
			return root;
		}
	}

	public static void main(String[] args) {

	}
}
